package class3;


import common.ListNode;
import common.ListNodeUtils;

/**
 * 两个链表相加：
 * 4 -> 3 -> 6
 * 2 -> 5 -> 3
 * 返回： 6 -> 8 -> 9
 * 634+325 = 986;
 */
public class Code07_LinkedAdd {
    public static void main(String[] args) {
        int[] arr1 = new int[]{4, 3, 6};
        int[] arr2 = new int[]{2, 5, 3};
        ListNode head1 = ListNodeUtils.getLinked(arr1);
        ListNode head2 = ListNodeUtils.getLinked(arr2);

        addTwoNumbers(head1, head2);
        ListNodeUtils.print(head1);
    }


    public static ListNode addTwoNumbers(ListNode head1, ListNode head2) {
        // 计算链表长度
        int len1 = getListLength(head1);
        int len2 = getListLength(head2);
        // 获取链表的长短
        ListNode l = len1 >= len2 ? head1 : head2;
        ListNode s = l == head1 ? head2 : head1;

        ListNode curL = l;
        ListNode curS = s;
        ListNode last = curL;
        int curNum = 0;
        int carry = 0; //进位
        while (curS != null) {
            curNum = curL.val + curS.val + carry;
            curL.val = (curNum % 10); // 取余
            carry = curNum / 10;  // 是否进位
            last = curL;
            curS = curS.next;
            curL = curL.next;
        }
        while (curL != null) {
            curNum = curL.val + carry;
            curL.val = curNum % 10;
            carry = curNum/10;
            last = curL;
            curL = curL.next;
        }
        if(carry!=0){
            last.next = new ListNode(1);
        }
        return l;
    }

    // 求链表长度
    public static int getListLength(ListNode listNode) {
        int size = 0;
        while (listNode != null) {
            size++;
            listNode = listNode.next;
        }
        return size;
    }

}
